#include<iostream>
#include<cstdio>
#include<limits>

#include"Util.h"
using namespace std;


//balance用来做平衡因子
//-1:左子树大
//0 :平衡状态
//1 :右子树大
struct TreeNode
{
    struct TreeNode *left;
    struct TreeNode *right;
    int value;
    int balance;
};

//下面对打印AVL进行一次特化
template<>
void Display<TreeNode>(const string& msg, TreeNode* root)
{

    //如果一个节点是NULL,则用这个来做占位
    TreeNode  Place;
    TreeNode *PlaceHolder=&Place; 

    //表示当前层的节点
    vector<TreeNode *> curLayer;
    //表示下一层的节点
    vector<TreeNode *> nextLayer;

    //取得树的深度
    int treeDepth=Depth<TreeNode>(root);

    //输出缓冲区
    char output[treeDepth][240];
    memset(output,' ',treeDepth*240);
    //设置字符串结束符
    for(int i=0; i<treeDepth; ++i)
        output[i][239]=0;

    bool flag=true;
    //初始工作
    curLayer.push_back(root);

    //当前节点用到的宽度
    int curWidth=64;
    //父节点用到的宽度
    int parentWidth=curWidth;
    //记录当前打印的第N层
    int layer=0;
    while(flag)
    {

        //表示当前节点是这一层Layer中首个被打印的节点
        bool first=true;
        //当前被打印节点在output中的位置
        int pos=0;

        //下面对curLayer进行遍历，对curLayer中的节点取得其左右子树保存到
        //nextLayer中
        for(int i=0; i<curLayer.size(); ++i)
        {
            TreeNode *tmp=curLayer[i];
            //curLayer中当前节点不为NULl
            if(tmp!=NULL && tmp!=PlaceHolder)
            {
                if(first)
                {
                    first=false;
                    //当前是第一个打印节点，也是当前层的第一个节点
                    if(i==0)
                        pos=curWidth;
                    //当前是第一个打印节点，但不是当前层的第一个节点,这里的currentWidth相当于第一个节
                    //点距离屏幕最左边的偏移，而没有加上currentWidth之前的pos则是该节点在当前层中的相对
                    //偏移位置
                    //
                    //|<------ curWidth ------> |<-------------------------pos节点偏移---------------------->|
                    //|<---离屏幕左边的偏移---> XX <---节点偏移---> XX <---节点偏移---> XX <---节点偏移---> XX
                    else
                        pos=pos+curWidth;
                }

                static const char balChar[3]={'/','-','\\'};
                //下面根据这个偏移在output输出缓冲区中打印相应的值
                int len=sprintf(&output[layer][pos],"%d(%c)",tmp->value,balChar[tmp->balance+1]);
                //这一步消除掉由sprintf打印时加的\0结束字符
                if(len>0)
                    output[layer][pos+len]=' ';
 
                //保存得到下一层的节点数据
                nextLayer.push_back(tmp->left);
                nextLayer.push_back(tmp->right);

            //这种情况需要用PlaceHolder来占一个位子
            }else if(tmp==NULL)
            {
                nextLayer.push_back(PlaceHolder);
                nextLayer.push_back(PlaceHolder);
            }

            //调整下一个节点输出的偏移
            pos+=parentWidth;
        }

        //计算下一层节点与当前节点的偏移
        parentWidth=curWidth;
        curWidth/=2;

        //下面做个检查，如果nextLayer中所有元素都是PlaceHolder，则此nextLayer就不
        //用处理了
        flag=false;
        for(int i=0; i<nextLayer.size(); ++i)
        {
            if(nextLayer[i]!=PlaceHolder && nextLayer[i]!=NULL)
            {
                flag=true;
                //交换nextLayer中的数据到curLayer中
                curLayer.swap(nextLayer);
                nextLayer.clear();
                break;
            }
        }
        ++layer;
    }

    //输出处理完后的内容
    cout<<msg<<endl;
    for(int i=0; i<treeDepth; ++i)
    {
        cout<<&output[i][0]<<endl;
    }
    cout<<endl;
}



//旋转函数
struct TreeNode *Rotate(struct TreeNode *root, struct TreeNode *child);
//辅助旋转函数
struct TreeNode *TurnLeft(struct TreeNode *root, struct TreeNode *child);
struct TreeNode *TurnRight(struct TreeNode *root, struct TreeNode *child);
//插入函数
struct TreeNode *Insert(int value, struct TreeNode *root, bool& is_taller);
//删除函数不写了先，太麻烦了，每次删除一个节点都要重新遍历调整平衡因子
struct TreeNode *Delete(int value, struct TreeNode *root, bool& is_shorter);

struct TreeNode *DelAux(struct TreeNode *parent, struct TreeNode *root, bool& is_shorter);

int main()
{
    bool flag=false;
    struct TreeNode *root=NULL;
    char msg[128]={0};
    int ch=0;
    cout<<"Enter the node, press 'e' or 'E' to end"<<endl;
    while(cin>>ch)
    {
        if(ch=='e' || ch=='E')
            break;

        flag=false;
        root=Insert(ch,root,flag);
        snprintf(msg,sizeof(msg),"insert %d:",ch);
        Display(msg,root);
    }

    cout<<"Delete the node, press 'e' or 'E' to end"<<endl;
    cin.clear();
    cin.ignore();
    while(cin>>ch)
    {
        if(ch=='e'||ch=='E')
            break;

        flag=false;
        root=Delete(ch,root,flag);
        snprintf(msg,sizeof(msg),"delete %d:",ch);
        Display(msg,root);
    }

    return 0;
}


struct TreeNode *Insert(int value, struct TreeNode *root, bool& is_taller)
{
    //当前是空节点，此时需要创建一个
	if(root==NULL)
	{
		root=(struct TreeNode *)malloc(sizeof(struct TreeNode));
		root->balance=0;
		root->left=root->right=NULL;
		root->value=value;
        is_taller=true;

		return root;
	}

    //处理左子树的情况
	if(value < root->value)
	{
        //递归处理
		root->left=Insert(value,root->left,is_taller);

        //左右子树不平衡，需要进行平衡处理
        if(is_taller)
        {
            switch(root->balance)
            {
                //当前是平衡状态，则在左子树插入一个新节点后，偏向左边
                case 0:
                    root->balance=-1;
                    break;

                //当前是右子树大，则现在为平衡状态
                case 1:
                    root->balance=0;
                    is_taller=false;
                    break;

                //当前是左子树大，则需要对左子树进行调整
                case -1:
                    root=Rotate(root,root->left);
                    is_taller=false;
                    break;
            }
        }
	}
	else if (value > root->value)
	{
        //在右子树插入新节点
		root->right=Insert(value,root->right,is_taller);
        //新节点需要进行调整
        if(is_taller)
        {
            switch(root->balance)
            {
                //当前平衡，现在偏向右边
                case 0:
                    root->balance=1;
                    break;

                //当前右子树大，则插入后需要调整右子树
                case 1:
                    root=Rotate(root,root->right);
                    is_taller=false;
                    break;

                case -1:
                    root->balance=0;
                    is_taller=false;
                    break;
            }
        }
    }

    return root;
}
                    
struct TreeNode *Rotate(struct TreeNode *root, struct TreeNode *child)
{
    if(root->balance==0)
    {
        return root;
    }

    //root的左子树大
    if(root->balance==-1)
    {
        //这种情况是图中的"Left Left Case"
        if(child->balance==-1)
        {
            //调整完后root和child都达到平衡状态
            root->balance=child->balance=0;
            return TurnRight(root,child);
        }
        //这种情况是图中的"Left Right Case"
        //要先处理这种结构为"Left Left Case“后，再进行旋转
        else if (child->balance==1)
        {
            root->balance=child->balance=0;

            child=TurnLeft(child,child->right);
            return TurnRight(root,child);
        }
    }
    //root的右子树大
    else if (root->balance==1)
    {
        //这种情况是"Right Left Case"
        //需要先处理成"Right Right Case"后再旋转
        if(child->balance==-1)
        {
            child->balance=root->balance=0;

            child=TurnRight(child,child->left);
            return TurnLeft(root,child);
        }
        //这种情况是"Right Right Case"
        else if(child->balance==1)
        {
            child->balance=root->balance=0;
            return TurnLeft(root,child);
        }
    }
    //此时child->balance==0
    return root;
}

//TurnLeft可以直接处理"Right Right Case",使它得到平衡
struct TreeNode * TurnLeft(struct TreeNode *root, struct TreeNode *child)
{
    root->right=child->left;
    child->left=root;
    return child;
}

//TurnRight可以直接处理"Left Left Case"
struct TreeNode * TurnRight(struct TreeNode *root, struct TreeNode *child)
{
    root->left=child->right;
    child->right=root;
    return child;
}


struct TreeNode *Delete(int value, struct TreeNode *root, bool& is_shorter)
{
    if(root==NULL)
        return NULL;

    if(value>root->value)
    {
        root->right=Delete(value,root->right,is_shorter);
        if(is_shorter)
        {
            //原来右倾，现在右子树减少一个节点，达到平衡
            if(root->balance==1)
            {
                root->balance=0;
                is_shorter=false;
            }

            //原来平衡，现在左倾
            else if (root->balance==0)
            {
                root->balance=-1;
                is_shorter=false;
            }

            //原来左倾，现在左倾更厉害
            else 
            {
                struct TreeNode *leftChild=root->left;
                //左子树平衡
                //跟踪得来
                //        13(/)                         7(\)
                //       /    \                        /    \
                //     7(-)    15                     5      13(-)
                //    /    \            =>                  /  \  
                //   5      10                             10   15
                //
                //
                //推演得来
                //        13(/)                         7(\)
                //       /    \                        /    \
                //     7(-)    15                     5      13(/)
                //    /    \            =>           / \    /  \  
                //   5      10                      4   6  10   15
                //  / \    /  \                           / \
                // 4   6  8    11                        8   11
                if(leftChild->balance==0)
                {
                    leftChild->balance=1;
                    root->balance=0;
                    //将leftChild以root为固定点向右旋转
                    root=TurnRight(root,leftChild);
                }
                //左子树左倾
                //        13(/)                         7(-)
                //       /    \                        /    \
                //     7(/)    15                     5      13(-)
                //    /                 =>           / \    /  \  
                //   5                              4   6  10   15
                //
                //
                else if (leftChild->balance==-1)
                {
                    root->balance=0;
                    leftChild->balance=0;

                    //将leftChild以root为固定点向右进行旋转
                    root=TurnRight(root,leftChild);

                }
                //左子树右倾
                //        13(/)                         13(/)                    10(-)
                //       /    \                        /    \                    /    \
                //     7(\)    15                    10      15                7(-)    13(-)
                //         \            =>          /  \             =>       /   \    /   \
                //          10                    7(\)  12                   5     8  12   15
                //                               /    \               
                //                              5      8                
                else if (leftChild->balance==1)
                {
                    
                    leftChild->right!=NULL?leftChild->right->balance=0:NULL;
                    leftChild->balance=0;
                    root->balance=0;
                    //将leftChild的右子树以leftChild为固定点向左旋转
                    leftChild=TurnLeft(leftChild,leftChild->right);
                    //将leftChild以root为固定点向右旋转
                    root=TurnRight(root,leftChild);
                    
                }
                is_shorter=false;
            }

        }
    }
    else if(value<root->value)
    {
        root->left=Delete(value,root->left,is_shorter);
        if(is_shorter)
        {
           if(root->balance==-1)
            {
                root->balance=0;
                is_shorter=false;
            }
            //原来平衡，现在达到右倾
            else if (root->balance==0)
            {
                root->balance=1;
            }
            //原来右倾，现在右倾地得厉害
            else
            {
                struct TreeNode *rightChild=root->right;
                //右子树左倾
                //        13(\)                     13(\)                          17(-)
                //       /    \                    /    \                          /    \
                //      7    18(/)                7      17                     13(-)    18(-)
                //           /   \       =>             /  \                    /   \    /   \
                //          17    20                   14   18(/)              7    14  15   20
                //         /  \                            /  \ 
                //        14  15                         15    20     
                if(rightChild->balance==-1)
                {
                    rightChild->left!=NULL?rightChild->left->balance=0:NULL;
                    root->balance=0;
                    rightChild->balance=0;
                    rightChild=TurnRight(rightChild,rightChild->left);
                    root=TurnLeft(root,rightChild);

                //右子树平衡
                //
                //跟踪而来的图
                //        13(\)                      18(/)           
                //       /    \                     /     \
                //      7    18(-)               13(-)     20          
                //           /    \       =>    /  \
                //          17     20          7   17    
                //
                //
                //
                //        13(\)                      18(/)           
                //       /    \                     /     \
                //      7    18(-)               13(\)     20          
                //           /    \       =>    /  \      /  \
                //          17     20          7   17    19  25          
                //         /  \   /  \            /  \
                //        14  15 19  25          14  15                
                }else if (rightChild->balance==0)
                {
                    rightChild->balance=-1;
                    root->balance=0;
                    root=TurnLeft(root,rightChild);

                //右子树右倾
                //        13(\)                          17(-)
                //       /    \                          /    \
                //      7      17(\)                 13(-)    18(-)
                //            /  \      =>           /   \    /   \
                //          14    18                7    14  15   20
                //               /  \
                //             15    20     
                }else if (rightChild->balance==1)
                {
                    root->balance=0;
                    rightChild->balance=0;
                    root=TurnLeft(root,rightChild);
                }
                is_shorter=false;
            }
        }
    }
    //找到要删除的节点
    else
    {
        //叶子节点
        if(root->left==NULL && root->right == NULL)
        {
            delete root;
            is_shorter=true;
            return NULL;
        }
        //左子空为空，右子树不为空
        else if (root->left==NULL && root->right!=NULL)
        {
            struct TreeNode *tmp=root->right;
            delete root;
            is_shorter=true;
            return tmp;
        }
        else if(root->left!=NULL)
        {
            //进行rightMost节点的查找，现在如果root->left变短，则要在root节
            //点的balance中表现出来
            root->left=DelAux(root->left,root,is_shorter);
            if(is_shorter)
            {
                if(root->balance==0)
                {
                    root->balance=1;
                }
                else if(root->balance==-1)
                {
                    root->balance=0;
                    is_shorter=false;
                }
                //删除节点7,root节点8
                //            15(/)                    15(/)
                //          /       \                /       \
                //        8(\)      25             8(\)      25
                //       /    \     /  \          /    \     /  \
                //     5(-)   10   20  28   =>  5(/)   10   20  28
                //     /  \  /  \        \      /     /  \        \
                //    4    7 9  11       30    4      9  11       30
                //               \                        \
                //               12                       12
                //
                //
                //
                //            15(/)                     15(-)
                //          /       \                /       \
                //         9        25             9(-)      25
                //       /   \     /  \          /    \     /  \
                //      5(-) 10   20  28   =>  5(-)   11   20  28
                //     /  \    \        \      /  \   / \        \
                //    4(-)8(-) 11       30    4   8  10 12       30
                //              \
                //              12
                //
                else if(root->balance==1)
                {
                    cout<<"NOTHING"<<endl;
                }
            }
        }
    }

    return root;
}
struct TreeNode *DelAux(struct TreeNode *root, struct TreeNode *delnode, bool& is_shorter)
{
    if(root==NULL)
        return NULL;

    //继续递归处理
    if(root->right!=NULL)
    {
        root->right=DelAux(root->right,delnode,is_shorter);
        if(is_shorter)
        {
            //去掉rightMost节点后，rightMost的父节点的balance要进行变化，但只有在
            //balance==-1的时候才需要对父节点进行调整
            struct TreeNode *tmp=root->right->left;
            delete root->right;
            root->right=tmp;

            //对于处于平衡状态的子树，不需要进行调整，所以is_short=false
            if(root->balance==0)
            {
                root->balance=-1;
                is_shorter=false;
            }
            //对于从不平衡达到平衡的子树，需要从下往上回溯进行调整
            else if (root->balance==1)
            {
                root->balance=0;
            }
            else if(root->balance==-1)
            {
                struct TreeNode *leftChild=root->left;
                // 6是root节点，8为删除节点
                //        9(/)                    9(/)
                //       /    \                 /      \
                //     6(/)    11              4(\)     11
                //    /   \   /  \            /   \     / \
                //   4(-)  8 10  12   =>     2    6(/) 10 12
                //  / \                           /
                // 2   5                         5
                if(leftChild->balance==0)
                {
                    root->left=leftChild->right;
                    leftChild->right=root;
                    root=leftChild;
                }
                // 6是root节点，8为删除节点
                //        9(/)                    9(-)
                //       /    \                 /      \
                //     6(/)    11              4(-)     11
                //    /   \   /  \            /   \     / \
                //   4(/)  8 10  12   =>     2    6(-) 10 12
                //  /                             
                // 2    
                else if(leftChild->balance==-1)
                {
                    leftChild->right=root;
                    leftChild->balance=0;
                }
                // 6是root节点，8为删除节点
                //        9(/)                9(/)                    9(-)
                //       /    \              /    \                  /     \
                //     6(/)    11          6(/)   11                5(-)    11
                //    /   \   /  \          /     / \              /   \   /  \
                //   4(\)  8 10  12   =>   5     10 12  2   =>    4   6(-) 10 12
                //    \                   /                      
                //     5                 4                       
                else if(leftChild->balance==1)
                {
                    leftChild->balance=0;
                    root->balance=0;
                    leftChild=TurnLeft(leftChild,leftChild->right);
                    root=TurnRight(root,leftChild);
                    is_shorter=false;
                }
            }
        }
    }
    //已经找到rightMost节点
    else
    {
        delnode->value=root->value;
        is_shorter=true;
        if(delnode->left==root)
        {
            if(root->left!=NULL)
            {
                root->value=root->left->value;
                root->balance=root->left->balance;
                delete root->left;
                root->left=NULL;
            }
            else
            {
                delete root;
                root=NULL;
            }
        }
    }
    return root;
}

